package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/8/22 21:55
 * @DESCRIPTION
 */
//给你一棵二叉树的根节点，返回该树的 直径 。
// 二叉树的 直径 是指树中任意两个节点之间最长路径的长度 。
// 这条路径可能经过也可能不经过根节点 root 。
// 两节点之间路径的 长度 由它们之间边数表示。
public class 二叉树的直径 {
    public int method1(TreeNode root) {
        int[] res = recursion(root);
        return res[1];
    }

    private int[] recursion(TreeNode root) {
        if(root==null){
            return new int[]{0,0};
        }
        int[] leftMaxDepth = recursion(root.left);
        int[] rightMaxDepth=recursion(root.right);
        int res=Math.max(Math.max(leftMaxDepth[1],rightMaxDepth[1]),leftMaxDepth[0]+rightMaxDepth[0]);
        int depth=Math.max(leftMaxDepth[0],rightMaxDepth[0])+1;
        return new int[]{depth,res};
    }

    int res=0;
    public int practice(TreeNode root) {
       if(root==null){
           return res;
       }
       recursionPractice(root);//返回的是二叉树最大直径的节点数
       return res-1;//因此返回结果时需要-1 才是最大直径
    }
    //这边的返回值是左子树或右子树最长链的节点数
    private int recursionPractice(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=recursionPractice(root.left);
        int right=recursionPractice(root.right);
        res=Math.max(right+left+1,res);
        return  Math.max(left,right)+1;
    }

    public int practice2(TreeNode root) {
        recursionPractice2(root);
        return res;
    }
    //返回值是该节点的最大深度
    private int recursionPractice2(TreeNode node) {
        if(node==null){
            return 0;
        }
        int leftDepth = recursionPractice2(node.left);
        int rightDepth = recursionPractice2(node.right);
        res=Math.max(leftDepth+rightDepth,res);
        return Math.max(leftDepth,rightDepth)+1;
    }
}
